import java.util.Random;

public class Test01 {
    public int[] sortArray(int[] nums) {
        qsort(nums,0 , nums.length -1);
        return nums;
    }

    private static void qsort(int[] nums, int l , int r){
        //递归出口
        if(l >= r) return;

        //数组分三块
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1 ,right = r+1 , i = l;
        while(i < right){
            if(nums[i] < key){
                swap(nums , ++left, i++);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,--right , i);
            }
        }
        //继续划分
        qsort(nums, l , left);
        qsort(nums,right , r);
    }

    private static void swap(int[] nums , int a , int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
